#pragma once
#include<iostream>
#include<stack>
using namespace std;

template<class T>
struct BITreeNode
{
    BITreeNode<T>* left;
    BITreeNode<T>* right;
    T _val;

    BITreeNode(const T& t=T()):left(nullptr), right(nullptr),_val(t)
    {}
};

template<class T>
class BITree
{
    typedef BITreeNode<T> Node;
public:
    BITree()=default;
    ~BITree()
    {
        _Destroy(_root);
    }
    
    void PreOrder()
    {
        _PreOrder(_root);
    }
    //非递归版本的中序遍历
    void InOrder()
    {
        _Inorder(_root);
    }
    void PostOrder()
    {
        _PostOrder(_root);
    }
    int countNode()
    {
        return _countNode(_root);
    }
    int _countNode(Node* root)
    {
        if(root == nullptr) 
            return 0;
        return _countNode(root->left) + _countNode(root->right) + 1;
    }
    int countLeaves()
    {
        return _countLeaves(_root);
    }
    int Depth()
    {
        return Depth(_root);
    }
    int Depth(Node* root)
    {
        if(!root)
            return 0;
        return max(Depth(root->left), Depth(root->right))+1;
    }
    int _countLeaves(Node* root)
    {
        if(root == nullptr) 
            return 0;
        if(!root->left&&!root->right)
            return 1;
        return _countNode(root->left) + _countNode(root->right);
    }
    void _Inorder(Node* root)
    {
        stack<BITreeNode<int>*> st;
        Node* cur = root;
        while(cur||!st.empty())
        {
            while(cur)
            {
                st.push(cur);
                cur = cur->left;
            }
            cur = st.top();
            st.pop();
            cout<<cur->_val<<' ';

            cur = cur->right;
        }
    }
    
    void _PostOrder(Node* root)
    {
        if(!root)   return;

        _PostOrder(root->left);
        _PostOrder(root->right);
        cout<<root->_val<<' ';
    }
    void _Destroy(Node* root)
    {
        if(_root == nullptr)    return;
        _Destroy(root->left);
        _Destroy(root->right);
        delete root;
    }
    void _PreOrder(Node* root)
    {
        if(root == nullptr) return;

        cout<<root->_val<<' ';
        _PreOrder(root->left);
        _PreOrder(root->right);
    }
    Node* _root=nullptr;

};


